package com.explorati.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.explorati.queue.ArrayQueue;

/**
 * 树的递归实现
 * 
 * @author explorati
 *
 * @param <E>
 */
public class BST<E extends Comparable<E>> {

	private class Node<E> {
		public E e;
		public Node left;
		public Node right;

		public Node(E e, Node left, Node right) {
			this.e = e;
			this.left = left;
			this.right = right;
		}

		public Node(E e) {
			this(e, null, null);
		}

		public String toString() {
			return e.toString();
		}
	}

	private Node root;
	private int size;

	public BST() {
		root = null;
		size = 0;
	}

	// 第一种实现
	// public void add(E e) {
	// if (root == null) {
	// root = new Node(e);
	// size++;
	// } else {
	// add(root, e);
	// }
	// }
	//
	// private void add(Node parent, E e) {
	// if (e.equals(parent.e)) {
	// return;
	// } else if (e.compareTo((E) parent.e) < 0 && parent.left == null) {
	// parent.left = new Node(e);
	// size++;
	// return;
	// } else if (e.compareTo((E) parent.e) > 0 && parent.right == null) {
	// parent.right = new Node(e);
	// size++;
	// return;
	// }
	//
	// if (e.compareTo((E) parent.e) < 0) {
	// add(parent.left, e);
	// } else {
	// add(parent.right, e);
	// }
	// }

	// 改进后的实现
	// 添加元素
	public void add(E e) {
		root = add(e, root);
	}

	// 返回插入新节点后的二分搜索树的根
	private Node add(E e, Node node) {
		if (node == null) {
			node = new Node(e);
			size++;
			return node;
		}
		// if (e.compareTo((E) node.e) == 0) {
		// return node;
		// }
		if (e.compareTo((E) node.e) > 0) {
			node.right = add(e, node.right);
		} else if (e.compareTo((E) node.e) < 0) {
			node.left = add(e, node.left);
		}
		return node;
	}

	public boolean contains(E e) {
		return contains(e, root);
	}

	public boolean contains(E e, Node node) {
		if (node == null) {
			return false;
		}

		if (e.equals(node.e)) {
			return true;
		} else if (e.compareTo((E) node.e) > 0) {
			return contains(e, node.right);
		} else {
			return contains(e, node.left);
		}
	}

	// 前序遍历
	public void preOrder() {
		preOrder(root);
	}

	// 前序遍历以node为根的二分搜索树
	private void preOrder(Node node) {
		// if (node == null) {
		// return;
		// }
		if (node != null) {
			System.out.println(node);
			preOrder(node.left);
			preOrder(node.right);
		}
	}

	// 前序遍历(非递归)
	public void preOrder1(Node node) {
		Stack<Node> stack = new Stack<Node>();
		if (node == null) {
			return;
		}
		stack.push(node);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			System.out.println(cur.e + "\t");
			if (cur.right != null) {
				stack.push(cur.right);
			}
			if (cur.left != null) {
				stack.push(cur.left);
			}
		}
	}

	// 中序遍历(递归实现)
	public void inOrder() {
		inOrder(root);
	}

	private void inOrder(Node node) {
		if (node == null) {
			return;
		}

		inOrder(node.left);
		System.out.println(node);
		inOrder(node.right);
	}

	// 中序遍历从小到大(非递归实现)
	public void inOrder2(Node node) {
		Stack<Node> stack = new Stack<Node>();
		if (node == null) {
			return;
		}
		Node cur = node;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			cur = stack.pop();
			System.out.println(cur.e);
			cur = cur.right;

		}
	}

	// 中序遍历从大到小(非递归实现)
	public void inOrder1() {
		Stack<Node> stack = new Stack<>();
		if (root == null) {
			return;
		}
		Node cur = root;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.right;
			}
			cur = stack.pop();
			System.out.println(cur.e + "\t");
			cur = cur.left;
		}
	}

	// 后序遍历(非递归实现)
	public List<E> postOrder() {
		ArrayList<E> list = new ArrayList<>();
		if (root == null) {
			return null;
		}
		Stack<Node> stack = new Stack<>();
		Stack<E> output = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			output.push((E) cur.e);

			if (cur.left != null) {
				stack.push(cur.left);
			}
			if (cur.right != null) {
				stack.push(cur.right);
			}
		}

		while (!output.isEmpty()) {
			list.add(output.pop());
		}
		return list;
	}

	public void levelOrder() {
		levelOrder(root);
	}

	// 层序遍历(使用Queue),广度优先遍历
	// 意义：用于搜索策略上，更快的找到问题的解，最短路径
	private void levelOrder(Node node) {
		if (node == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(node);
		while (!queue.isEmpty()) {
			Node cur = queue.remove();
			System.out.println(cur.e);

			if (cur.left != null) {
				queue.add(cur.left);
			}

			if (cur.right != null) {
				queue.add(cur.right);
			}
		}
	}

	// 寻找二分搜索树的最小元素
	public E minmum() {
		if (size == 0) {
			throw new IllegalArgumentException("BST is empty!");
		}

		return (E) minmum(root).e;
	}

	private Node minmum(Node node) {

		if (node.left == null) {
			return node;
		}

		return minmum(node.left);
		// while (node.left != null) {
		// node = node.left;
		// }
		// return (E) node.e;

	}

	// 寻找二分搜索树的最大元素
	public E maxmum() {
		if (size == 0) {
			throw new IllegalArgumentException("BST is empty!");
		}
		return (E) maxmum(root).e;
	}

	private Node maxmum(Node node) {
		if (node.right == null) {
			return node;
		}
		return maxmum(node.right);
	}

	// 从二分搜索树中删除最小值所在节点，并返回最小值
	public E removeMin() {
		E ret = minmum();
		root = removeMin(root);
		return ret;
	}

	// 删除掉以node为节点的二分搜索树的最小节点
	// 返回删除节点后新的二分搜索树的根
	private Node removeMin(Node node) {
		if (node.left == null) {
			Node rightNode = node.right;
			node.right = null;
			size--;
			return rightNode;
		}

		node.left = removeMin(node.left);
		return node;
	}

	public E removeMax() {
		E ret = maxmum();
		root = removeMax(root);
		return ret;
	}

	private Node removeMax(Node node) {
		if (node.right == null) {
			Node leftNode = node.left;
			node.left = null;
			size--;
			return leftNode;
		}
		node.right = removeMax(node.right);
		return node;
		// 错误的，最后的cur = leftNode只是将cur指向了leftCode，没有改变树
		// Node cur = node;
		// while (cur.right != null) {
		// cur = cur.right;
		// }
		// if (cur.left == null) {
		// cur = null;
		// }
		// if (cur.left != null) {
		// Node leftNode = cur.left;
		// cur.left = null;
		// cur = null;
		// cur = leftNode;
		// }
		// return node;
	}

	// 从而分搜索树中删除元素为e的节点
	public void remove(E e) {
		root = remove(root, e);
	}

	// 删除以node为根的二分搜索树中值为e的节点，递归算法
	// 返回删除节点后二分搜索树的根
	private Node remove(Node node, E e) {
		if (node == null) {
			return null;
		} else if (e.compareTo((E) node.e) < 0) {
			node.left = remove(node.left, e);
			return node;
		} else if (e.compareTo((E) node.e) > 0) {
			node.right = remove(node.right, e);
			return node;
		} else { // e == node.e
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				size--;
				return rightNode;
			} else if (node.right == null) {
				Node leftNode = node.left;
				node.left = null;
				size--;
				return leftNode;
			} else {
				// 待删除节点的左右节点都不为空的情况
				// 找到比待删除节点大的最小节点，即待删除节点的右子树的最小节点
				// 用这个节点顶替待删除节点的位置
				Node successor = minmum(node.right);
				successor.right = removeMin(node.right);
				successor.left = node.left;

				node.left = node.right = null;

				return successor;
			}
		}
	}

	public int getSize() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
}
